#include <SDL/SDL.h>
#include <SDL/SDL_ttf.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "ArbreBinaire.h"
#include "SDLDraw.h"

arbre creerArbre(char eti, int val, SDL_Surface* support)
{
	arbre res = malloc(sizeof(struct ArbreBinaire));

	res->etiquette = eti;
	res->valeur = val;
	res->support = support;

	res->hauteur = 1;
	res->filsg = NULL;
	res->filsd = NULL;
	res->pere = res;
	res->xCurrent = -1;
	res->yCurrent = -1;
	res->currentRayonCercle = -1;
}

int estFeuille(arbre noeud)
{
	if (noeud == NULL)
	{
		perror("estFeuille : l'arbre paramètre est NULL");
		exit(EXIT_FAILURE);
	}

	return ((noeud->filsg == NULL) && (noeud->filsd == NULL));
}

int getHauteur(arbre noeud)
{
	int res = 0;
	int hauteurg;
	int hauteurd;

	if (noeud != NULL)
	{
		res++;

		if ((hauteurd = getHauteur(noeud->filsd)) >= (hauteurg = getHauteur(noeud->filsg)))
			res += hauteurd;
    	else
    		res += hauteurg;
	}

	return res;
}

// Met à jour les hauteurs de chacun des noeuds de la racine
void setHauteurs(arbre racine)
{
	if (racine == NULL)
	{
		perror("setHauteurs : l'arbre paramètre est NULL");
		exit(EXIT_FAILURE);
	}

	racine->hauteur = getHauteur(racine);

	if (racine->filsg != NULL) 
		setHauteurs(racine->filsg);

	if (racine->filsd != NULL)
		setHauteurs(racine->filsd);
}

int getDesequilibre(arbre noeud)
{
	if (noeud == NULL)
	{
		perror("getDesequilibre : l'arbre paramètre est NULL");
		exit(EXIT_FAILURE);
	}
	
	int res = 0;

	if (noeud->filsd != NULL)
	{
		res = (noeud->filsd)->hauteur;
	}

	if (noeud->filsg != NULL)
	{
		res -= (noeud->filsg)->hauteur;
	}

	return res;
}

void parcoursPrefix(arbre racine)
{
	if (racine != NULL)
	{
		if (racine->pere == racine)
			printf("	%c : %d (hauteur : %d, père : /)\n", racine->etiquette, racine->valeur, racine->hauteur);
		else
			printf("	%c : %d (hauteur : %d, père : %c)\n", racine->etiquette, racine->valeur, racine->hauteur, racine->pere->etiquette);

		parcoursPrefix(racine->filsg);
		parcoursPrefix(racine->filsd);
	}
}

void rotationGauche(arbre noeud)
{
	// Dessiner des flêches à coté des noeuds qu'on va rotater pour indiquer leur sens de rotation
	drawFlecheArbre(noeud->support, noeud->xCurrent, noeud->yCurrent, noeud->currentRayonCercle, 1, 1);
	drawFlecheArbre(noeud->support, (noeud->filsd)->xCurrent, (noeud->filsd)->yCurrent, (noeud->filsd)->currentRayonCercle, 0, 0);

	SDL_Flip(noeud->support);

	// Afficher ces flêches durant 3 secondes
	SDL_Delay(3000);

	// Si le noeud déséquilibré est la racine de l'arbre
	if (noeud->pere == noeud)
	{
		// Sauvegarder les données de l'ancienne racine
		arbre copieAncienneRacine = creerArbre(noeud->etiquette, noeud->valeur, noeud->support);
		arbre ancienFilsDroit = noeud->filsd;
		arbre ancienFilsGauche = noeud->filsg;

		// Mettre à jour la racine
		noeud->etiquette = ancienFilsDroit->etiquette;
		noeud->valeur = ancienFilsDroit->valeur;
		noeud->filsd = ancienFilsDroit->filsd;
		(noeud->filsd)->pere = noeud;

		// Créer la partie de gauche du nouvelle arbre avec la copie de l'ancienne racine
		noeud->filsg = copieAncienneRacine;
		copieAncienneRacine->pere = noeud;

		copieAncienneRacine->filsd = ancienFilsDroit->filsg;
		if (copieAncienneRacine->filsd != NULL)
			(copieAncienneRacine->filsd)->pere = copieAncienneRacine;

		copieAncienneRacine->filsg = ancienFilsGauche;
		if (copieAncienneRacine->filsg != NULL)
			(copieAncienneRacine->filsg)->pere = copieAncienneRacine;

		// L'ancien fils droit a été copié dans la racine et n'est plus utilisé, il peut être libéré
		free(ancienFilsDroit);
	}
	else
	{
		// Le noeud à rotater est-il le fils droit ou le fils gauche de son père ? Selon la réponse, créer le même lien avec le noeud qui va le remplacer
		if (noeud == (noeud->pere)->filsd)
			(noeud->pere)->filsd = noeud->filsd;
		else
			(noeud->pere)->filsg = noeud->filsd;

		(noeud->filsd)->pere = noeud->pere;

		// Mettre à jour le noeud à rotater (créer un lien avec son nouveau père puis lui greffer son ancien fils gauche)
		noeud->pere = noeud->filsd;

		noeud->filsd = (noeud->pere)->filsg;
		if ((noeud->pere)->filsg != NULL)
			((noeud->pere)->filsg)->pere = noeud;

		(noeud->pere)->filsg = noeud;
	}
}

void rotationDroite(arbre noeud)
{
	// Dessiner des flêches à coté des noeuds qu'on va rotater pour indiquer leur sens de rotation
	drawFlecheArbre(noeud->support, noeud->xCurrent, noeud->yCurrent, noeud->currentRayonCercle, 0, 1);
	drawFlecheArbre(noeud->support, (noeud->filsg)->xCurrent, (noeud->filsg)->yCurrent, (noeud->filsg)->currentRayonCercle, 1, 0);

	SDL_Flip(noeud->support);

	// Afficher ces flêches durant 3 secondes
	SDL_Delay(3000);

	// Si le noeud déséquilibré est la racine de l'arbre
	if (noeud->pere == noeud)
	{
		// Sauvegarder les données de l'ancienne racine
		arbre copieAncienneRacine = creerArbre(noeud->etiquette, noeud->valeur, noeud->support);
		arbre ancienFilsDroit = noeud->filsd;
		arbre ancienFilsGauche = noeud->filsg;

		// Mettre à jour la racine
		noeud->etiquette = ancienFilsGauche->etiquette;
		noeud->valeur = ancienFilsGauche->valeur;
		noeud->filsg = ancienFilsGauche->filsg;
		(noeud->filsg)->pere = noeud;

		// Créer la partie de droite du nouvelle arbre avec la copie de l'ancienne racine
		noeud->filsd = copieAncienneRacine;
		copieAncienneRacine->pere = noeud;

		copieAncienneRacine->filsg = ancienFilsGauche->filsd;
		if (copieAncienneRacine->filsg != NULL)
			(copieAncienneRacine->filsg)->pere = copieAncienneRacine;

		copieAncienneRacine->filsd = ancienFilsDroit;
		if (copieAncienneRacine->filsd != NULL)
			(copieAncienneRacine->filsd)->pere = copieAncienneRacine;

		// L'ancien fils gauche a été copié dans la racine et n'est plus utilisé, il peut être libéré
		free(ancienFilsGauche);
	}

	else
	{
		// Le noeud à rotater est-il le fils droit ou le fils gauche de son père ? Selon la réponse, créer le même lien avec le noeud qui va le remplacer
		if (noeud == (noeud->pere)->filsg)
			(noeud->pere)->filsg = noeud->filsg;
		else
			(noeud->pere)->filsd = noeud->filsg;

		(noeud->filsg)->pere = noeud->pere;

		// Mettre à jour le noeud à rotater (créer un lien avec son nouveau père puis lui greffer son ancien fils droit)
		noeud->pere = noeud->filsg;

		noeud->filsg = (noeud->pere)->filsd;
		if ((noeud->pere)->filsd != NULL)
			((noeud->pere)->filsd)->pere = noeud;

		(noeud->pere)->filsd = noeud;
	}
}


void equilibrer(arbre racine, arbre noeud)
{
	if (noeud != NULL)
	{
		int desequilibre = getDesequilibre(noeud);

		if (desequilibre == 2)
		{
			int desequilibreDroit = getDesequilibre(noeud->filsd);

			if (desequilibreDroit == 0 || desequilibreDroit == 1)
			{
				printf("Simple rotation gauche\n");

				rotationGauche(noeud);

				setHauteurs(racine);
			}
			else if (desequilibreDroit == -1)
			{
				printf("Double rotation droite-gauche\n");

				rotationDroite(noeud->filsd);

				// Afficher l'arbre après la première rotation durant 1 seconde
				clearScreen(racine->support);
				drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
				SDL_Flip(racine->support);
				SDL_Delay(1000);

				rotationGauche(noeud);

				setHauteurs(racine);
			}
		}
		else if (desequilibre == -2)
		{
			int desequilibreGauche = getDesequilibre(noeud->filsg);

			if (desequilibreGauche == -1 || desequilibreGauche == 0)
			{
				printf("Simple rotation droite\n");

				rotationDroite(noeud);

				setHauteurs(racine);
			}
			else if (desequilibreGauche == 1)
			{
				printf("[Double rotation gauche-droite]\n");

				rotationGauche(noeud->filsg);

				// Afficher l'arbre après la première rotation durant 1 seconde
				clearScreen(racine->support);
				drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
				SDL_Flip(racine->support);
				SDL_Delay(1000);

				rotationDroite(noeud);

				setHauteurs(racine);
			}
		}
		else
		{
			// Si on n'a pas encore atteint la racine
			if (noeud != noeud->pere)
				equilibrer(racine, noeud->pere);
		}
	}

	// Afficher l'arbre une nouvelle fois une fois les deux rotations effectuées
	clearScreen(racine->support);
	drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
	SDL_Flip(racine->support);
}

arbre rechercherArbre(arbre racine, char etiquette/*, int valeur*/)
{
	if (racine != NULL)
	{
		/*arbre arbreCourant = racine;

		while (1)
		{
			if (etiquette == arbreCourant->etiquette && valeur == arbreCourant->valeur) {
				return arbreCourant;
			}
			else if (valeur > arbreCourant->valeur)
			{
				if (arbreCourant->filsd == NULL)
					return NULL;
				else
					arbreCourant = arbreCourant->filsd;
			}
			else
			{
				if (arbreCourant->filsg == NULL)
					return NULL;
				else
					arbreCourant = arbreCourant->filsg;
			}
		}*/

		arbre res = NULL;

		// Si l'arbre recherché est la racine
		if (etiquette == racine->etiquette) {
			return racine;
		}
		else {
			// Rechercher l'arbre dans le fils gauche de l'arbre courant s'il possède un fils fauche
			if (racine->filsg != NULL) {
				res = rechercherArbre(racine->filsg, etiquette);
			}

			// Si l'arbre n'a pas été trouvé dans le fils gauche et qu'il possède un fils droit, le rechercher dans ce dernier
			if (res == NULL && racine->filsd != NULL) {
				res = rechercherArbre(racine->filsd, etiquette);
			}
		}

		return res;
	}

	return NULL;
}

arbre insererArbre(arbre racine, arbre insertion)
{
	if (insertion == NULL)
	{
		perror("insererArbre : l'arbre à insérer est NULL");
		exit(EXIT_FAILURE);
	}

	// Si on essaye d'insérer un arbre dans une racine vide, cet arbre devient la racine qu'on renvoie après l'avoir affiché
	if (racine == NULL) {
		racine = insertion;

		clearScreen(racine->support);
		drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
		SDL_Flip(racine->support);

		return racine;
	}

	printf("Insertion de %d\n", insertion->valeur);

	arbre arbreCourant = racine;

	while (1)
	{
		if (insertion->valeur > arbreCourant->valeur)
		{
			if (arbreCourant->filsd == NULL)
			{
				arbreCourant->filsd = insertion;
				insertion->pere = arbreCourant;

				break;
			}
			else
			{
				arbreCourant = arbreCourant->filsd;
			}
		}
		else
		{
			if (arbreCourant->filsg == NULL)
			{
				arbreCourant->filsg = insertion;
				insertion->pere = arbreCourant;

				break;
			}
			else
			{
				arbreCourant = arbreCourant->filsg;
			}
		}
	}

	// Mettre à jour les hauteurs de chacun des noeuds de la racine
	setHauteurs(racine);

	// Afficher l'arbre et son nouveau noeud
	clearScreen(racine->support);
	drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
	SDL_Flip(racine->support);

	// Equilibrer l'arbre si nécessaire
	equilibrer(racine, insertion->pere);

	printf("Résultat :\n");
	parcoursPrefix(racine);

	return racine;
}

arbre supprimerArbre(arbre racine, arbre suppression) {
	// Si l'arbre à supprimer de possède aucun fils
	if (suppression->filsg == NULL && suppression->filsd == NULL) {
		// Si c'est la racine, il ne reste plus aucun noeud et on sort du programme
		if (suppression->pere == suppression) {
			free(racine);

			printf("Fin du programme\n");

			exit(EXIT_SUCCESS);
		}
		else {
			// Sinon, supprimer le lien qu'il a avec son père (selon qu'il soit son fils gauche ou son fils droit)
			if (suppression == (suppression->pere)->filsg)
				(suppression->pere)->filsg = NULL;
			else
				(suppression->pere)->filsd = NULL;
		}
	}
	// Si l'arbre à supprimer possède uniquement un fils droit
	else if (suppression->filsg == NULL) {
		// Si c'est la racine, elle est le dernier noeud de l'arbre avec son fils droit, c'est donc ce dernier qui deviendra racine. On remplace alors les attributs de la racine par ceux de son fils droit, qui devient le noeud à supprimer
		if (suppression->pere == suppression) {
			racine->etiquette = (racine->filsd)->etiquette;
			racine->valeur = (racine->filsd)->valeur;

			suppression = racine->filsd;

			racine->filsd = NULL;
		}
		else {
			// Sinon, relier le père de l'arbre à supprimer avec le fils droit de ce dernier (le remonter d'un cran)
			if (suppression == (suppression->pere)->filsg)
				(suppression->pere)->filsg = suppression->filsd;
			else
				(suppression->pere)->filsd = suppression->filsd;

			(suppression->filsd)->pere = suppression->pere;
		}
	}
	// Si l'arbre à supprimer possède uniquement un fils gauche
	else if (suppression->filsd == NULL) {
		// Si c'est la racine, elle est le dernier noeud de l'arbre avec son fils gauche, c'est donc ce dernier qui deviendra racine. On remplace alors les attributs de la racine par ceux de son fils gauche, qui devient le noeud à supprimer
		if (suppression->pere == suppression) {
			racine->etiquette = (racine->filsg)->etiquette;
			racine->valeur = (racine->filsg)->valeur;

			suppression = racine->filsg;

			racine->filsg = NULL;
		}
		// Sinon, relier le père de l'arbre à supprimer avec le fils gauche de ce dernier (le remonter d'un cran)
		else {
			if (suppression == (suppression->pere)->filsg)
				(suppression->pere)->filsg = suppression->filsg;
			else
				(suppression->pere)->filsd = suppression->filsg;

			(suppression->filsg)->pere = suppression->pere;
		}
	}
	// Si l'abre possède ces deux fils
	else {
		char suppressionEtiquette = suppression->etiquette;
		int suppressionValeur = suppression->valeur;

		arbre arbreCourant = suppression->filsd;

		// Chercher le successeur de l'arbre à supprimer, et, une fois trouvé, l'intervertir avec l'arbre à supprimer. Supprimer ensuite l'arbre à supprimer (qui se retoruve dans l'un des cas traités plus haut)
		while (1) {
			if (arbreCourant->filsg != NULL) {
				if ((arbreCourant->filsg)->valeur >= suppression->valeur) {
					arbreCourant = arbreCourant->filsg;
				}
			}
			else {
				suppression->etiquette = arbreCourant->etiquette;
				suppression->valeur = arbreCourant->valeur;

				arbreCourant->etiquette = suppressionEtiquette;
				arbreCourant->valeur = suppressionValeur;

				clearScreen(racine->support);
				drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
				SDL_Flip(racine->support);
				SDL_Delay(2000);
				
				return supprimerArbre(racine, arbreCourant);
			}
		}
	}

	// Mettre à jour les hauteurs de chacun des noeuds de la racine
	setHauteurs(racine);

	// Afficher l'arbre
	clearScreen(racine->support);
	drawArbreBinaire(racine->support, racine, SCREEN_WIDTH, SCREEN_HEIGHT, racine->hauteur, 0, 1, -1, -1);
	SDL_Flip(racine->support);

	// L'équilibrer si nécessaire
	equilibrer(racine, suppression->pere);

	printf("Résultat :\n");
	parcoursPrefix(racine);

	// Libérer le noeud qu'on vient de supprimer
	free(suppression);

	return racine;
}

void drawArbreBinaire(SDL_Surface* surface, arbre arbre, int screenWidth, int screenHeight, int hauteurRacine, int profondeur, int index, int xPere, int yPere) {
   	// Position du noeud sur l'axe des abscisses en fonction de son index et de sa profondeur
    float xCoeff = (float)index / (pow(2, profondeur) + 1.0);
    float x = xCoeff * (float)screenWidth;

    // Position du noeud sur l'axe des ordonnées en fonction de sa profondeur et de la hateur de la racine
    float yCoeff = (float)profondeur / (float)(hauteurRacine);
    float y = (yCoeff * (float)screenHeight) + (((float)screenHeight / (float)(hauteurRacine)) / 2.0);

    // Rayons maximaux des cercles des sommets en fonction de la taille de l'écran
    float rayonMaxHauteur = ((float)screenHeight / (float)(hauteurRacine)) / 2.0;
    float rayonMaxLargeur = ((float)screenWidth / (pow(2, hauteurRacine - 1))) / 3.0;

    float rayonCercle = MIN(rayonMaxHauteur, rayonMaxLargeur);

    // Mettre à jour les coordonnées actuelles du noeud sur l'écran
    arbre->xCurrent = x;
    arbre->yCurrent = y;
    arbre->currentRayonCercle = rayonCercle;

    // Dessiner le cercle du noeud
    drawCircle(surface, x, y, rayonCercle, 0);

    // Ecriture de l'étiquette de l'arbre et de sa valeur
    TTF_Font *font = TTF_OpenFont("arial.ttf", rayonCercle / 1.5);
    SDL_Color textColor = {0, 0, 0};
    
    char etiquetteArbre[255];
    sprintf(etiquetteArbre, "%c", arbre->etiquette);

    char valeurArbre[255];
    sprintf(valeurArbre, "%d", arbre->valeur);
   
    SDL_Surface* surfaceEtiquetteArbre = TTF_RenderText_Blended(font, etiquetteArbre, textColor); 
    SDL_Surface* surfaceValeurArbre = TTF_RenderText_Blended(font, valeurArbre, textColor); 

    applySurface(x - (surfaceEtiquetteArbre->w / 2), y - surfaceEtiquetteArbre->h - ((rayonCercle - surfaceEtiquetteArbre->h) / 2), surfaceEtiquetteArbre, surface);   
    drawLine(surface, x - rayonCercle, y, x + rayonCercle, y, 0);
    applySurface(x - (surfaceValeurArbre->w / 2), y + ((rayonCercle - surfaceValeurArbre->h) / 2), surfaceValeurArbre, surface);

    TTF_CloseFont(font);

    // Si le noeud n'est pas le noeud racine, le relier à son père
    if (arbre->pere != arbre) {
        drawLine(surface, xPere, yPere, x, y, 0);
    }

    // Dessiner les fils du noeud en prenant soin de leur passer leur profondeur et leur index ainsi que les coordonnées de leur père
    if (arbre->filsg != NULL) {
        drawArbreBinaire(surface, arbre->filsg, screenWidth, screenHeight, hauteurRacine, profondeur + 1, index * 2 - 1, x, y);
    }

    if (arbre->filsd != NULL) {
        drawArbreBinaire(surface, arbre->filsd, screenWidth, screenHeight, hauteurRacine, profondeur + 1, index * 2, x, y);
    }
}